import React, { Component } from "react";
import Sort, { BubbleSort, HeapSort, InsertSort, MergeSort, QuickSort, SelectSort, ShellSort } from "./Algorithms";
// import MDRenderer from "./MDRenderer";
import { gradientColor } from "./Common";
import levels from './Levels.json';

const MAX_SIZE = 500;

const Sort_Algs = [
  {key:"bubble", value:"冒泡排序"},
  {key:"insert", value:"插入排序"},
  {key:"select", value:"选择排序"},
  {key:"shell", value:"希尔排序"},
  {key:"merge", value:"归并排序"},
  {key:"quick", value:"快速排序"},
  {key:"heap", value:"堆排序"},
]

export default
class TSort extends Component {
  
  constructor(props) {
    super(props);

    this.state = {
      size: 5,
      repeatable: false,
      
      unsorted: [],
      quickSortTree: {},
      splitedList:{},
      listMask: [],
      enableMask: true,
      counter:[],
      buckets:[],
      bucketSize: 3,

      autoHeapify:false,

      isSorted: -1,
      isReverse: false,

      sortAlgorithm: Sort_Algs[0].key,

      indexA: -1,
      indexB: -1,
      autoSwap: true,
      swapCount: 0,
      
      startColor: '#1982cc',
      endColor: '#ff0000',
      colorMap: [],
      showIndex: true,
      showLegend: false,

      animateDelta: 500,
      algorithmInfo: '# 算法解析',

      level:0,
      difficulty:'0',
      shellGap:1,

      message:'',

    }

    this.handleValueChanged = this.handleValueChanged.bind(this);
    this.handleRandomData = this.handleRandomData.bind(this);
    this.onSetGameLevel = this.onSetGameLevel.bind(this);
    this.onDataClicked = this.onDataClicked.bind(this);
    this.onSwapData = this.onSwapData.bind(this);
    this.onRunSorting = this.onRunSorting.bind(this);
    this.onRunStep = this.onRunStep.bind(this);
    this.onRunLoop = this.onRunLoop.bind(this);
    this.onRunAnimation = this.onRunAnimation.bind(this);
    this.onSetSortAlgorithm = this.onSetSortAlgorithm.bind(this);
    this.onLoadMDFile = this.onLoadMDFile.bind(this);

    this.switchConfigure = this.switchConfigure.bind(this);

    this.sort = new Sort();

    this.nodeMap = new Map();
    this.heapLength = 5;

  }

  componentDidMount() {
    const lv = 0;
    this.setState({ level: lv });
    this.initGame(this.state.size, lv, this.state.difficulty);
    this.updateColorMap( this.state.startColor, this.state.endColor, this.state.size );

  }

  updateColorMap( startColor, endColor, size ) {

    const colorMap = gradientColor( startColor, endColor, size );
    this.setState({ 
      colorMap: colorMap 
    });

  }

  resetState() {
    this.setState({
      splitedList: [], 
      autoHeapify: false,
      quickSortTree:{},
      enableMask:true,

      swapCount: 0,
      indexA: -1,
      indexB: -1
    })

    // this.initCounter(this.state.size);
    // this.initBuckets(this.state.bucketSize);
  }

  resetGame() {
    
    const level = parseInt(this.state.level);

    if( this.sort ) {
      this.sort.reset();
    }

    this.createDataMask(this.state.size, this.state.difficulty);

    this.setState({
      unsorted: this.sort.unsorted,
    })

    if( level === 9 ) {
      this.initCounter(this.state.size);
    }

    if( level === 10 ){
      this.initBuckets( this.state.bucketSize );
    }

    this.resetState();
    this.heapLength = this.state.size;
  }

  clearCompare() {
    this.setState({
      indexA: -1,
      indexB: -1
    })
  }

  newGame() {
    this.initGame( this.state.size, this.state.level, this.state.difficulty);    
  }

  initGame( size, level, difficulty ) {
    this.createRandomData( size, level );
    this.createDataMask( size, difficulty );

    if( level === 9 ) {
      this.initCounter( size );
    }

    if( level === 10 ){
      this.initBuckets( this.state.bucketSize );
    }
  }

  onSetGameLevel(event) {
    const id = event.target.id;
    var level = this.state.level;

    if( id ==='inc' && level < levels.length-1 ) {
      level++;
    }
    else if( id === 'dec' && level > 0 ) {
      level--;
    }
    else{
      return;
    }

    this.setState({ level: level });
    this.initGame( this.state.size, level, this.state.difficulty );
  }

  createRandomData( size, level ) {

    size = size < 2 ? 2 : size > MAX_SIZE ? MAX_SIZE : size;

    var dataMode = this.state.repeatable? 3 : 2;

    if( level === 0 ) {
      dataMode = Math.floor( Math.random() * 4 );
    }

    this.sort.randomData( size, dataMode );
    this.heapLength = size;

    this.setState({
      unsorted: this.sort.unsorted,
    })

    this.resetState();

  }

  createDataMask( size, difficulty ) {
    const mask = [];
    
    for( var i = 1; i <= size; i++ ) {
      if( difficulty === '0' ){
        mask.push(0);
      }
      else if( difficulty === '2' ){
        mask.push(1);
      }else{
        mask.push(0);
      }
    }

    this.setState({enableMask: true, listMask: mask});
    
  }

  handleValueChanged( event ) {
    const id = event.target.id;

    switch( id ) {
      case 'startColor':
        this.setState({startColor: event.target.value});
        this.updateColorMap( event.target.value, this.state.endColor, this.state.size );
        break;
      case 'endColor':
        this.setState({endColor: event.target.value});
        this.updateColorMap( this.state.startColor, event.target.value, this.state.size );
        break;
      case 'size':
        if( event.target.value < 2 ) return;
        this.setState({size: event.target.value});
        this.updateColorMap( this.state.startColor, this.state.endColor, event.target.value );
        this.initGame( event.target.value, this.state.level, this.state.difficulty );
        break;
      case 'showIndex':
        this.setState({showIndex: event.target.checked});
        break;
      case 'showLegend':
        this.setState({showLegend: event.target.checked});
        break;
      case 'animateDelta':
        this.setState({animateDelta: event.target.value});
        break;
      case 'isReverse':
        this.sort.isReverse = event.target.checked;
        this.sort.resetCount();
        this.setState({isReverse: event.target.checked});
        break;
      case 'autoSwap':
        this.setState({autoSwap: event.target.checked});
        break;
      case 'shellGap':
        const gap = parseInt(event.target.value);
        if( gap <= 0 || gap > this.state.size / 2 ) break;
        this.setState({shellGap: event.target.value});
        break;
      case 'level':
        this.setState({level: parseInt(event.target.value)});
        this.initGame( this.state.size, parseInt(event.target.value), this.state.difficulty );

        break;
      case 'autoHeapify':
        const autoHeapify = event.target.checked;
        if(autoHeapify) {
          this.onHeapify();
        }
        this.setState({autoHeapify: autoHeapify});
        break;
      case 'repeatable':
        this.setState({repeatable: event.target.checked});
        break;
      case 'bucketSize':
        const bucketSize = parseInt(event.target.value);
        if( bucketSize > this.state.size || bucketSize <= 0 ) return;
        this.setState({bucketSize: bucketSize});
        this.initBuckets( bucketSize );
        break;
        // case 'sortAlgorithm':
      //   this.setState({sortAlgorithm: event.target.value});
      //   break;
      default:
        break;
    }

  }

  handleRandomData( event ) {
    this.createRandomData( this.state.size, this.state.level );
  }

  onSetSortAlgorithm( event ) {
    const key = event.target.value;
    const unsorted = this.state.unsorted;
    const isReverse = this.state.isReverse;

    switch(key){
      case 'bubble':
        this.sort = new BubbleSort(unsorted, isReverse);
        break;
      case 'insert':
        this.sort = new InsertSort(unsorted, isReverse);
        break;
      case 'select':
        this.sort = new SelectSort(unsorted, isReverse);
        break;
      case 'shell':
        this.sort = new ShellSort(unsorted, isReverse);
        break;
      case 'merge':
        this.sort = new MergeSort(unsorted, isReverse);
        break;
      case 'quick':
        this.sort = new QuickSort(unsorted, isReverse);
        break;
      case 'heap':
        this.sort = new HeapSort(unsorted, isReverse);
        break;
      default:
        this.sort = new BubbleSort(unsorted, isReverse);
        break;
    }

    this.setState({
      sortAlgorithm : key
    });

    this.loadMDFile( `./${key}.md` );
    // this.refLoad.current.click();
  }

  onDataClicked( event ) {
    const index = parseInt( event.target.id );
    const level = this.state.level;
    const indexA = this.state.indexA;
    const indexB = this.state.indexB;

    switch (level) {
      case 0:
        this.switchDataMask( index );
        break;
      case 1:
      case 7:
        if( index !== indexB ){
          this.setCompareData( indexB, index );
        }
        break;
      case 2:
        this.setCompareData( index, index + 1 );
        break;
      case 3:
        if( indexA < 0 ) {
          this.setCompareData( index, -1 );
        }
        else{
          this.setCompareData( indexA, index );
        }
        break;
      case 4:
        this.setCompareData( index - 1, index );
        break;
      // shell sort
      case 5:
        const gap = this.state.shellGap;
        this.setCompareData( index - gap, index );
        break;
      // count sort
      case 9:
        this.moveToCounter(index);
        break;
      case 10:
        this.moveToBucket(index);
        break;
      default:
        break;
    }
  }

  setCompareData( indexA, indexB ) {
    if( indexA >= this.sort.size() ){
      indexA = -1;
    }
    if( indexB >= this.sort.size() ){
      indexB = -1;
    }

    this.setState({
      indexA: indexA,
      indexB: indexB
    })
  }

  lockIndex( event ) {
    const id = event.target.id;

    if( id === '0' ) {
      this.setState({isLockedA: !this.state.isLockedA});
    }
    else if ( id === '1' ) {
      this.setState({isLockedB: !this.state.isLockedB});
    }
  }

  switchDataMask( index ) {
    const indexA = this.state.indexA;
    const difficulty = this.state.difficulty;
    if( difficulty === '0' ) return;

    if( indexA >= 0 ) {
      this.setDataMask( indexA, 1 );
    }
    this.setDataMask( index, 0 );
    
    this.setState({
      indexA: index
    })
  }

  setDataMask( i, m ) {
    const mask = this.state.listMask;
    mask[i] = m;

    this.setState({
      listMask: mask
    })
  }

  setGameDifficulty( event ){
    const difficulty = event.target.value;
    
    this.setState({ difficulty: difficulty });

    this.initGame( this.state.size, this.state.level, difficulty );

  }

  onMergeNode(event) {
    const id = event.target.id;
    const node = this.nodeMap.get(id);

    const left = node.left.data;
    const right = node.right.data;

    node.data = this.merge( left, right );
    

    if( id ==='root' ) {
      this.sort.set(node.data);

      this.setState({
        unsorted: this.sort.unsorted,
        splitedList: {}
      })
    }

    this.forceUpdate();
  }

  merge( left, right ) {
    var result = [];
    while( left.length && right.length ) {
      if( left[0] <= right[0] ) {
        result.push(left.shift())
      }
      else{
        result.push(right.shift())
      }
    }

    while (left.length)
      result.push(left.shift());

    while (right.length)
      result.push(right.shift());

    return result;
  }

  onLoadMDFile( ) {
    const alg = this.state.sortAlgorithm;
    this.loadMDFile( `./${alg}.md` );
  }

  loadMDFile( url ) {

    fetch(url).then(response=>{
      return response.text();
    }).then(md=>{
      this.setState({ algorithmInfo: md })
    })

  }

  switchConfigure() {
    this.setState({ showLegend: !this.state.showLegend });
  }

  onRunStep( event ) {
    if( !this.sort ) return;

    const ret = this.sort.doOneStep();
    event.target.style.color = ret ? 'green' : 'black';

    this.setState({
      indexA: this.sort.stepCount,
      indexB: this.sort.loopCount,
      swapCount: this.sort.swapCount,
      isSorted: this.sort.check(),
    })

  }

  onRunLoop(event) {
    if( !this.sort ) return;

    const ret = this.sort.doOneLoop();
    event.target.style.color = ret ? 'green' : 'black';

    this.setState({
      indexA: this.sort.stepCount,
      indexB: this.sort.loopCount,
      swapCount: this.sort.swapCount,
      isSorted: this.sort.check(),
    })

    return ret;
  }

  onRunSorting() {
    if( !this.sort ) return;

    this.sort.run();

    this.setState({
      swapCount: this.sort.swapCount,
      isSorted: this.sort.check(),
    })

  }

  onRunAnimation( event ) {
    if( !this.sort ) return;

    const isFinished = this.onRunLoop( event );
    if( !isFinished ) {
      window.setTimeout( this.onRunAnimation, this.state.animateDelta, event );
    }

  }

  swap( ia, ib ) {

    const level = this.state.level;

    this.sort.swap( ia, ib );

    this.setState({
      swapCount: this.sort.swapCount,
      isSorted: this.sort.check(),
    });

    // 选择排序 交换后清空索引
    switch(level){
      case 2:
        this.setCompareData( ib, ib + 1 );
        break;
      case 3:
        this.setCompareData(-1, -1)
        break;
      case 4:
        this.setCompareData( ia-1, ia );
        break;
      // shell sort
      case 5:
        const gap = this.state.shellGap;
        this.setCompareData( ia-gap, ia );
        break;
      default:
        break;
    }
    
  }

  check( arr ) {
    
    if( arr.length < 2 ) return -1;

    var isReverse = arr[1] < arr[0];

    for( var i = 2, il = arr.length; i < il; i++ ) {
      if( isReverse && arr[i] >= arr[i - 1] ) {
        return 0;
      }
      else if( !isReverse && arr[i] <= arr[i-1] ){
        return 0;
      }
    }

    if( isReverse ) {
      return 2;
    }
    else {
      return 1;
    }

  }

  onSwapData ( event ) {

    const indexA = this.state.indexA;
    const indexB = this.state.indexB;
    
    if( indexA < 0 || indexB < 0 ) return;

    this.swap( indexA, indexB );

  }

  renderData() {
    const data = this.state.unsorted;
    const mask = this.state.listMask;
    const colorMap = this.state.colorMap;
    const size = this.state.size;
    const indexA = this.state.indexA;
    const indexB = this.state.indexB;
  
    return(
      <div className="data-viewer">
        {data.map(( value, index )=>{
          var percent = Math.floor((value * 100) / size);
          
          const style={
            background: `linear-gradient(to top, ${colorMap[value-1]} 0%, ${colorMap[value-1]} ${percent}%, white ${percent}%, white)`
          }

          if( percent <= 0 ) {
            style.background = `white`;
          }

          const hidden = index !== indexA && index !== indexB && this.state.enableMask && mask[index] > 0;
          
          if( hidden ) {
            style.background = 'gray';
          }
          
          return(
            <div className="data" key={index}>
              <div className="value">{ hidden ?'?':value}</div>
              <div className="figure" style={style} id={index} onClick={this.onDataClicked} ></div>
              <div className="index">{this.state.showIndex?index:""}</div>
            </div>
          ) 
        })}
      </div>
    )

  }

  renderSplitedData() {
    const level = this.state.level;
    // 适用于归并排序
    if( level !== 6 ) return;

    const node = this.state.splitedList;

    return this.createNodeView(node);

  }

  createNodeView( node ) {
    if( !node ) return;

    const data = node.data;
    const colorMap = this.state.colorMap;
    const size = this.state.size;
    if( !data || data.length <= 0 ) return;

    this.nodeMap.set(node.id, node);

    return(
      <div className="node-viewer">
        <div className="data-viewer">
        {data.map(( value, index )=>{
          const percent = Math.floor((value * 100) / size);
          
          const style={
            background: `linear-gradient(to top, ${colorMap[value-1]} 0%, ${colorMap[value-1]} ${percent}%, white ${percent}%, white)`
          }
          
          return(
            <div className="data" key={index}>
              <div className="value">{value}</div>
              <div className="figure" style={style} id={index}></div>
              <div className="index">{this.state.showIndex?index:""}</div>
            </div>
          ) 
        })}
        </div>
        {(node.left && node.left.data.length>0)||(node.right&& node.right.data.length>0)?
          <button onClick={this.onMergeNode.bind(this)} id={node.id}>归并</button>
          :""
        }
        {(node.left && node.left.data.length>0)||(node.right&& node.right.data.length>0)?
          <div className="children">
            <div className="left">{this.createNodeView(node.left)}</div>
            <div className="right">{this.createNodeView(node.right)}</div>
          </div>
          :""
        }
      </div>
    )
  }

  renderMenu() {
    return (
      <div className="menu-panel">
        {this.state.showLegend?
          <div className="items" hidden={!this.state.showLegend}>
            <label>显示索引</label>
            <input type='checkbox' id="showIndex" checked={this.state.showIndex} onChange={this.handleValueChanged} />
            <label>起始颜色</label>
            <input type="color" id="startColor" value={this.state.startColor} onChange={this.handleValueChanged}/>
            <label>结束颜色</label>
            <input type="color" id="endColor" value={this.state.endColor} onChange={this.handleValueChanged}/>
            <label>动画间隔</label>
            <input type="number" id="animateDelta" value={this.state.animateDelta} onChange={this.handleValueChanged}/>
          </div>
          :""
        }

        <label>选择关卡:&nbsp;&nbsp;</label>
        <select id='level' value={this.state.level} onChange={this.handleValueChanged}>
          {levels.map((item,index)=>
            <option value={item.lv} key={index}>{item.title}</option>
          )}
        </select>

        <label>简单</label>
        <input type='radio' name='difficulty' value='0' checked={this.state.difficulty==='0'} onChange={this.setGameDifficulty.bind(this)}></input>
        {/* <label>容易</label>
        <input type='radio' name='difficulty' value='1' checked={this.state.difficulty==='1'} onChange={this.setGameDifficulty.bind(this)}></input> */}
        <label>困难</label>
        <input type='radio' name='difficulty' value='2' checked={this.state.difficulty==='2'} onChange={this.setGameDifficulty.bind(this)}></input>
       
        <div style={{flex:'1'}}></div>
        <label className="clickable" id='dec' onClick={this.onSetGameLevel}>上一关</label>
        <label className="clickable" id='inc' onClick={this.onSetGameLevel}>下一关</label>
        
        <label className="clickable" onClick={this.switchConfigure}>设置</label>
        {/* <input type='checkbox' id="showLegend" checked={this.state.showLegend} onChange={this.handleValueChanged}/> */}
        <label className="clickable">帮助</label>
      </div>
    )
  }

  renderDataCreator() {
    return (
      <div className="creator">
        <label>数据大小:&nbsp;&nbsp;</label>
        <input type="number" id="size" value={this.state.size} onChange={this.handleValueChanged}/>
        <label>可重复:&nbsp;&nbsp;</label>
        <input type='checkbox' id='repeatable' checked={this.state.repeatable} onChange={this.handleValueChanged}></input>
        <button onClick={this.resetGame.bind(this)}>重新开始</button>
        <button onClick={this.newGame.bind(this)}>新游戏</button>
      </div>
    );
  }

  renderQuickSort() {
    const level = this.state.level;
    if( level !== 7 ) return;

    // this.nodeMap.clear();
    // const node = {range:[0, this.state.size-1], id:'root'};

    return this.createQuickSortTree(this.state.quickSortTree);
  }

  renderDataHeap() {
    const level = this.state.level;
    if( level !== 8 ) return;

    const heapLength = this.heapLength;
    if( heapLength === 0 ) return;

    const arr = this.state.unsorted.slice(0, heapLength);
    const node = { parent:0 };
    this.createHeap( arr, node );
    
    return this.createHeapView( node );
  }

  createHeap( arr, node ) {
    if( !node ) return;

    const r = node.parent;
    const left = 2 * r + 1;
    const right = 2 * r + 2;

    if( left < arr.length ) {
      node['left'] = { parent:left };
    }

    if( right < arr.length ) {
      node['right'] = {parent: right};
    }

    this.createHeap( arr, node.left );
    this.createHeap( arr, node.right );
  }

  adjustHeap( event ) {
    const id = event.target.id.split('@');
    const action = id[0];
    const index = parseInt(id[1]);

    switch(action){
      case 'pick':
        --this.heapLength;
        this.swapData(0, this.heapLength);

        if( this.state.autoHeapify ) {
          this.heapify(0);
        }

        break;

      case 'left':
        var left = 2 * index + 1;
        this.swapData( index, left );
        break;
      case 'right':
        var right = 2 * index + 2;
        this.swapData( index, right );
        break;
      case 'up':
        const isLeft = index % 2 === 1;
        var parent = isLeft ? (index-1)/2 : (index-2)/2;
        this.swapData(parent, index);
        break;
      default:
        break;
    }

    this.forceUpdate();
  }

  onHeapify(event) {
    // 生成最大堆
    if(this.heapLength === this.state.size) {
      this.buildMaxHeap();
    }
    // 调整堆
    else{
      this.heapify(0);
    }

    this.forceUpdate();
  }

  swapData( ia, ib ) {
    const arr = this.state.unsorted;
    const tmp = arr[ia];
    arr[ia] = arr[ib];
    arr[ib] = tmp;
  }

  buildMaxHeap() {
    const arr = this.state.unsorted;
    for (var i = Math.floor(arr.length/2); i >= 0; i--) {
      this.heapify(i);
    }
    this.forceUpdate();
  }

  heapify(r) {
    const arr = this.state.unsorted;
    const len = this.heapLength; 
    
    var left = 2*r + 1;
    var right = 2*r + 2;
    var largest = r;

    if (left < len && arr[left] > arr[largest]) {
      largest = left;
    }

    if (right < len && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest !== r) {
      this.swapData(r, largest);
      this.heapify(largest);
    }
  }

  createHeapView( node ) {
    if( !node ) return;

    const arr = this.state.unsorted;
    const data = arr[node.parent];
    const startColor = this.state.startColor;
    const endColor = this.state.endColor;
    const size = this.state.size;
    const deg = Math.floor( 360 / size );

    const style = {
      background : `conic-gradient( ${startColor} ${data*deg}deg, ${endColor} ${data*deg}deg )`
    }

    return(
      <div className="node-viewer">
        <button className="align-center" hidden={node.parent===0} id={`up@${node.parent}`} onClick={this.adjustHeap.bind(this)}>上</button>
        <div hidden={node.parent!==0}>
        <button id={`pick@${node.parent}`} onClick={this.adjustHeap.bind(this)}>取出</button>
        <label>自动调整<input type="checkbox" id='autoHeapify' checked={this.state.autoHeapify} onChange={this.handleValueChanged}/></label>
        </div>
        <div className="pie" style={style}>
          <label>{data}</label>
        </div>
        <label>{node.parent}</label>
        <div className="children">
          <div className="left" id={node.parent}>
            {node.left?
              <button className="align-right" id={`left@${node.parent}`} onClick={this.adjustHeap.bind(this)}>左</button>
              :""
            }
          </div>
          <div className="right" id={node.parent}>
            {node.right?
              <button className="align-left" id={`right@${node.parent}`} onClick={this.adjustHeap.bind(this)}>右</button>
              :""
            }
          </div>
        </div>
        <div className="children">
          <div className="left">{this.createHeapView(node.left)}</div>
          <div className="right">{this.createHeapView(node.right)}</div>
        </div>
        <div>
        <button hidden={node.parent!==0} id={`pick@${node.parent}`} onClick={this.onHeapify.bind(this)}>调整堆</button>
        
        </div>
      </div>
    );
  }

  rearrange( event ) {
    const node = this.nodeMap.get( event.target.id );

    const low = node.range[0];
    const high = node.range[1];
    const arr = this.state.unsorted;

    const pivot = this.partition(arr, low, high);

    node['left'] = {
      range:[low, pivot - 1],
      id:node.id+'-l'
    }

    node['right'] = {
      range:[pivot+1, high],
      id:node.id+'-r'
    }

    this.forceUpdate();
  }

  onRearrange( event ) {
    const id = event.target.id.split('@');
    const node = this.nodeMap.get(id[0]);
    const left = node.range[0];
    const right = node.range[1];
    const index = parseInt(id[1]);
    const arr = this.state.unsorted;

    function swap( ia, ib ){
      const tmp = arr[ia];
      arr[ia] = arr[ib];
      arr[ib] = tmp;
    }

    function rearrange( mid, left, right ) {
      swap( mid, left );

      var pivot = left;
      var index = pivot + 1;

      for(var i = left; i <= right; i++){
        if(arr[i] < arr[pivot]){
          swap(i, index);
          ++index;
        }
      }
      swap( pivot, index-1 );

      return index - 1;
    }

    const pivot = rearrange(index, left, right);
    
    node['left'] = {
      range:[left, pivot - 1],
      id:node.id+'-l'
    }

    node['right'] = {
      range:[pivot+1, right],
      id:node.id+'-r'
    }

    this.forceUpdate();

  }

  partition(arr, low, high) {
    let pivot = arr[low];

    while (low < high) {
      while (low < high && arr[high] > pivot) {
        --high;
      }
      arr[low] = arr[high];
      while (low < high && arr[low] <= pivot) {
        ++low;
      }
      arr[high] = arr[low];
    }
    arr[low] = pivot;
    return low;
  }

  createQuickSortTree( node ) {
    if( !node ) return;
    const arr = this.state.unsorted;
    const range = node.range;
    const colorMap = this.state.colorMap;
    const size = this.state.size;

    if( !range || range[0] >= range[1] ) return;

    const data = arr.slice( range[0], range[1] + 1 );

    this.nodeMap.set(node.id, node);

    return(
      <div className="node-viewer">
        <div className="data-viewer">
        {data.map(( value, index )=>{
          const percent = Math.floor((value * 100) / size);
          
          const style={
            background: `linear-gradient(to top, ${colorMap[value-1]} 0%, ${colorMap[value-1]} ${percent}%, white ${percent}%, white)`
          }
          
          return(
            <div className="data" key={index}>
              <div className="value">{value}</div>
              <div className="figure" style={style} id={`${node.id}@${node.range[0] + index}`} onClick={this.onRearrange.bind(this)}></div>
              <div className="index">{this.state.showIndex?index:""}</div>
            </div>
          ) 
        })}
        </div>
        <button id={node.id} onClick={this.rearrange.bind(this)}>自动重排</button>
        <div className="children">
          <div className="left">{this.createQuickSortTree(node.left)}</div>
          <div className="right">{this.createQuickSortTree(node.right)}</div>
        </div>
      </div>
    )
  }

  splitUnsorted( node ) {

    if(!node.data || node.data.length <= 1) return;
    const data = node.data;
    const middle = Math.floor(data.length/2);
    node['left'] = {
      data: data.slice(0, middle),
      id: node.id+'-l'
    }
    node['right'] = {
      data: data.slice(middle),
      id: node.id+'-r'
    }
    this.splitUnsorted(node.left);
    this.splitUnsorted(node.right);

  }

  onSplitList(){
    const node ={data:this.state.unsorted, id:'root'};
    this.nodeMap.clear();

    this.splitUnsorted(node);
    
    this.setState({
      splitedList: node
    })
  }

  onCreateQuickSortRoot() {
    this.setState({
      quickSortTree: {range:[0, this.state.size-1], id:'root'}
    });
  }

  renderCompare() {
    const level = this.state.level;
    if( level === 0 ) return;

    // 归并排序
    if( level === 6 ) {
      return(
        <div className="compare">
          <div className="row">
            <div className="data">
              <button onClick={this.onSplitList.bind(this)}>一键分割</button>
            </div>
          </div>
        </div>
      )
    }

    // 堆排序
    if( level === 8 ) {
      return(<label className="align-left">堆试图:</label>);
      // (
      //   <button onClick={this.buildMaxHeap.bind(this)}>生成最大堆</button>
      // )
    }

    // 计数排序
    if( level === 9 ) {
      return(
        <div className="compare">
          <div className="row">
            <div className="data">
              <button onClick={this.updateCounter.bind(this)}>一键统计</button>
            </div>
            <div className="data">
              <button onClick={this.fromCounter.bind(this)}>一键取出</button>
            </div>
          </div>
        </div>
      )
    }
    // 桶排序
    if( level === 10 ) {
      return(
        <div className="compare">
          <div className="row">
            <div className="data"><label>桶数量:</label></div>
            <div className="data"><input type='number' id="bucketSize" value={this.state.bucketSize} onChange={this.handleValueChanged}/></div>
          </div>
          <div className="row">
            <div className="data">
              <button onClick={this.updateBuckets.bind(this)}>一键统计</button>
            </div>
            <div className="data">
              <button onClick={this.fromBuckets.bind(this)}>一键取出</button>
            </div>
          </div>
        </div>
      )
    }

    const indexA = this.state.indexA;
    const indexB = this.state.indexB;
    const size = this.state.size;
    const startColor = this.state.startColor;
    const endColor = this.state.endColor;
    const deg = Math.floor( 360 / size );
    const unsorted = this.state.unsorted;

    let styleA = {
      borderColor: startColor,
      background: "white"
    };

    let styleB ={
      borderColor: endColor,
      background: "white"
    }

    const a = unsorted[indexA];
    const b = unsorted[indexB];

    if(a){
      styleA.background = `conic-gradient( ${startColor} ${a*deg}deg, white ${a*deg}deg )`;
    }

    if(b){
      styleB.background = `conic-gradient( ${endColor} ${b*deg}deg, white ${b*deg}deg )`;
    }

    return (
      <div className="compare">
        <div className="row">
          <div className="data"></div>
          {/* <div className="data">
            <label>自动交换</label>
            <input type='checkbox' id='autoSwap' checked={this.state.autoSwap} onChange={this.handleValueChanged} />
          </div> */}
          <div className="data"></div>
        </div>
        <div className="row">
          <div className="data pie" style={styleA}>
            <label>{a}</label>
          </div>
          <div className="data txt-xxxl">
            <label>{a&&b&&a>b?">":a<b?"<":"="}</label>
          </div>
          <div className="data pie" style={styleB}>
            <label>{b}</label>
          </div>
        </div>
        <div className="row">
          <div className="data txt-italic">
            <label>[{indexA >= 0 ? indexA:""}]</label>
            {/* <button id='0' onClick={this.lockIndex.bind(this)}>{this.state.isLockedA?"解锁":"锁定"}</button> */}
          </div>
          <div className="data">
            <button onClick={this.clearCompare.bind(this)}>清空</button>
            <button onClick={this.onSwapData}>交换</button>
          </div>
          <div className="data txt-italic">
            <label>[{indexB >= 0 ? indexB:""}]</label>
            {/* <button id='1' onClick={this.lockIndex.bind(this)}>{this.state.isLockedB?"解锁":"锁定"}</button> */}
          </div>
        </div>
        
        {(()=>{
          if(level === 5){
            return(
            <div className="row">
              <div className="data"></div>
              <div className="data">
                <label>增量</label>
                <input type='number' id="shellGap" value={this.state.shellGap} onChange={this.handleValueChanged}/>
              </div>
              <div className="data"></div>
            </div>
          )}
        })()}
        
        {level === 7?
          <div className="row">
            <div className="data"></div>
            <button onClick={this.onCreateQuickSortRoot.bind(this)}>分步演示</button>
            <div className="data"></div>
          </div>
          :""
        }
        {/* <div className="row">
          <div className="data" style={{background:this.state.isSorted===1?"green":"gray"}}>顺序</div>
          <div className="data">{this.state.swapCount}</div>
          <div className="data" style={{background:this.state.isSorted===2?"green":"gray"}}>逆序</div>
        </div> */}
      </div>
    );
  }

  initCounter( size ) {
    // const size = this.state.size;
    const counter = [];
    for( var i = 0; i < size; i++ ) {
      counter[i] = 0;
    }

    this.setState({
      counter: counter
    })

  }

  initBuckets( bucketSize ) {
    
    const buckets = [];
    for( var i = 0; i < bucketSize; i++ ) {
      buckets[i] = [];
    }

    this.setState({
      buckets:buckets
    })

  }

  updateCounter() {
    const unsorted = this.state.unsorted;
    const counter = this.state.counter;
    
    // reset count
    // for( let i = 0, il = unsorted.length; i < il; i++ ){
    //   counter[i] = 0;
    // }

    for( let i = 0, il = unsorted.length; i < il; i++ ){
      if( unsorted[i] <= 0 ) continue;
      ++counter[unsorted[i]-1];
      unsorted[i] = 0;
    }

    this.forceUpdate();
    // this.setState({
    //   unsorted:unsorted,
    //   counter:counter
    // })
  }

  updateBuckets() {
    const unsorted = this.state.unsorted;
    const buckets = this.state.buckets;
    const bucketSize = this.state.bucketSize;
    const capacity = Math.floor((unsorted.length + bucketSize - 1) / bucketSize);
    
    for(var i = 0, il = unsorted.length; i < il; i++) {
      if( unsorted[i] <= 0 ) continue;
      const j = Math.floor( (unsorted[i] - 1) / capacity );
      buckets[j].push(unsorted[i]);
      for( var k = buckets[j].length-1; k > 0; k-- ){
        if( buckets[j][k] >= buckets[j][k-1] )break;
        buckets[j][k] = buckets[j][k-1];
        buckets[j][k-1] = unsorted[i];
      }

      unsorted[i] = 0;
    }

    this.forceUpdate();

  }

  moveToCounter( index ) {
    const unsorted = this.state.unsorted;
    const counter = this.state.counter;
    const mask = this.state.listMask;

    if( unsorted[index] <= 0 ) return;
    
    mask[index] = 0;

    counter[unsorted[index]-1]++;
    unsorted[index] = 0;

    this.forceUpdate();
  }

  moveToBucket( index ) {
    const unsorted = this.state.unsorted;
    const buckets = this.state.buckets;
    const mask = this.state.listMask;

    const bucketSize = this.state.bucketSize;
    const capacity = Math.floor((unsorted.length + bucketSize - 1) / bucketSize);

    if( unsorted[index] <= 0 ) return;
    
    mask[index] = 0;

    const j = Math.floor( (unsorted[index] - 1) / capacity );
    buckets[j].push(unsorted[index]);
    for( var k = buckets[j].length-1; k > 0; k-- ){
      if( buckets[j][k] >= buckets[j][k-1] )break;
      buckets[j][k] = buckets[j][k-1];
      buckets[j][k-1] = unsorted[index];
    }

    unsorted[index] = 0;

    this.forceUpdate();
  }

  fromCounter( ) {
    const unsorted = this.state.unsorted;
    const counter = this.state.counter;
    var index = 0;
    for( var i = 0, il = counter.length; i < il; i++ ){
      while(counter[i] > 0) {
        unsorted[index++] = i + 1;
        counter[i]--;
      }
    }

    this.forceUpdate();
  }

  fromBuckets() {
    const unsorted = this.state.unsorted;
    const buckets = this.state.buckets;
    var index = 0;
    
    for( var i = 0, il = buckets.length; i< il; i++ ){
      while( buckets[i].length ) {
        unsorted[index++] = buckets[i].shift();
      }
    }

    this.forceUpdate();
  }

  moveOne() {
    const unsorted = this.state.unsorted;
    const counter = this.state.counter;
    var index = 0;
    
    while(index < unsorted.length && unsorted[index] > 0){
      ++index;
    }

    var i = 0;
    while(i < counter.length && counter[i] === 0){
      i++;
    }

    if( i < counter.length ) {
      unsorted[index] = i + 1;
      counter[i]--;
    }

    this.forceUpdate();
  }

  moveOneBucket() {
    const unsorted = this.state.unsorted;
    const buckets = this.state.buckets;
    var index = 0;
    
    while(index < unsorted.length && unsorted[index] > 0){
      ++index;
    }

    var i = 0;
    while(i < buckets.length && buckets[i].length <= 0){
      i++;
    }

    if( i < buckets.length ) {
      while( buckets[i].length ) {
        unsorted[index++] = buckets[i].shift();
      }
    }

    this.forceUpdate();
  }

  renderCountSort() {
    const level = this.state.level;
    if( level !== 9 ) return;

    const counter = this.state.counter;
    if( counter.length <= 0 ) return;

    return(
      <div className="counter-viewer">
        {counter.map(( value, index )=>{     
          return(
            <div className="data" key={index} onClick={this.moveOne.bind(this)}>
              <div className="clickable txt-bold">{value}</div>
              <div className="txt-italic">{index + 1}</div>
            </div>
          ) 
        })}
      </div>
    )
  }

  renderBuckets() {
    const level = parseInt(this.state.level);

    if( level !== 10 ) return;

    const buckets = this.state.buckets;

    return buckets.map((item, key)=>
      <div key={key} className="bucket-viewer">
        {
          item.map((value,index)=>
            <div className="data txt-bold" key={index}>{value}</div>
          )
        }
        <label className="head clickable" onClick={this.moveOneBucket.bind(this)}>{`${item.length} @ ${key}`}</label>
      </div>
    )
  }

  renderAlgorithms() {
    return(
      <div className="algorithm">
        <div className="row">
          <label>选择排序算法:</label>
          <select id="sortAlgorithm" value={this.state.sortAlgorithm} onChange={this.onSetSortAlgorithm}>
            {Sort_Algs.map((item)=>
              <option key={item.key} value={item.key}>{item.value}</option>
            )}
          </select>
          <label>&nbsp;</label>
          <label ref={this.refLoad} className="clickable" onClick={this.onLoadMDFile}>{"解析"}</label>
          <label>&nbsp;</label>
          <label>{this.state.isReverse?"逆序":"顺序"}</label>
          <input type='checkbox' id="isReverse" checked={this.state.isReverse} onChange={this.handleValueChanged}/>
        </div>
        <div className="row">
          <button onClick={this.onRunStep}>单步进行</button>
          <button onClick={this.onRunLoop}>单次循环</button>
          <button onClick={this.onRunSorting}>自动完成</button>
          <button onClick={this.onRunAnimation}>播放动画</button>
        </div>
      </div>
    );
  }

  renderTitle() {
    return(
      <div className="App-title">{levels[this.state.level].title}</div>
    );
  }

  renderHelper() {
    const helper = levels[this.state.level].helper
    return(
      <ol className="App-helper">{helper.map((item,key)=>
        <li key={key}>{item}</li>)}
      </ol>
    );
  }

  // 第一关 有序与无序
  gameOrder(){
    return(
      <div className="algorithm">
        <div className="row">
          <button id='0' onClick={this.onCheckAnswer.bind(this)}>无序</button>
          <button id='1' onClick={this.onCheckAnswer.bind(this)}>顺序</button>
          <button id='2' onClick={this.onCheckAnswer.bind(this)}>逆序</button>
        </div>
      </div>
    )
  }

  // 第二关 排序
  gameSort() {
    const level = this.state.level;
    const showSwapCount = level in [1, 2, 3, 4, 5];
    return(
      <div className="algorithm">
        <div className="row">
          <button id='0' onClick={this.onCheckAnswer.bind(this)}>完成</button>
          {showSwapCount
            ? <label>交换次数：[{this.state.swapCount}]</label>
            : ""
          }
        </div>
      </div>
    )
  }

  onCheckAnswer(event) {
    const ans = parseInt( event.target.id );
    const isSorted = this.sort.check();
    const level = this.state.level;

    const setMessage=( isRight )=>{
      this.setState({enableMask:false, message:isRight?'正确':'错误'});
    }
    switch(level){
      case 0:
        setMessage( ans === isSorted );
        break;
      default:
        setMessage( isSorted !== 0 );
        break;
    }    

    window.setTimeout(this.fadeMessage.bind(this), 500);
  }

  fadeMessage() {
    this.setState({message:''});
  }

  renderGame() {
    const level = this.state.level;
    switch(level){
      case 0:
        return this.gameOrder();        
      default:
        return this.gameSort();
    }
    
  }

  render() {
    return(
      <div className="main-panel">
        {this.renderTitle()}
        {this.renderMenu()}
        {this.renderHelper()}
        <div className='data-panel'>
          <div className="message">{this.state.message}</div>
          {this.renderData()}
          {this.renderDataCreator()}
          {this.renderCompare()}
          {this.renderSplitedData()}
          {this.renderQuickSort()}
          {this.renderDataHeap()}
          {this.renderCountSort()}
          {this.renderBuckets()}
        </div>
        <div className='ctrl-panel'>
          {/* {this.renderAlgorithms()} */}
          {this.renderGame()}
        </div>
        {/* <div className="md">
          <MDRenderer  Text={this.state.algorithmInfo}/>
        </div> */}
      </div>
    );
  }

}